class Solution {
public:
    string answerString(string word, int numFriends) {
        if(numFriends == 1) return word;
        int n = word.size();
        int maxsize = n - numFriends + 1;
        char mod = 0;
        int pos = 0;
        for(int i = 0;i < n;i++){
            if(word[i] > mod){
                mod = word[i];
                pos = i;
            }else if(word[i] == mod){
                for(int j = 1;j < maxsize;j++){
                    if(i + j < n && word[i + j] > word[pos + j]){
                        pos = i;
                        break;
                    }else if(word[i + j] < word[pos + j]){
                        break;
                    }
                }
            }
        }
        return word.substr(pos,maxsize);
    }
};
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(1003);
        int n = cost.size();
        dp[0] = cost[0],dp[1] = cost[1];
        for(int i = 2;i < n;i++){
            dp[i] = min(dp[i - 1],dp[i - 2]) + cost[i];
        }
        return min(dp[n - 1],dp[n - 2]);
    }
};

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        // sort(nums.begin(),nums.end());
        for (int k = 1; k <= target; k++) {
            for (int i : nums) {
                if(i <= k && dp[k - i] <= INT_MAX - dp[k])
                    dp[k] +=dp[k - i];
            }
        }
        return dp[target];
    }
};
// 1 2 3
// 1 0 0 0 0
// 1 1 1 1 1
// 1 1 2 2 3
//